package com.szrt.day20170407;


import org.junit.Test;
public class QuickSortTest {
	
	
	
	
	
	@Test
	public void sortTest() throws Exception {
		
		int[] array={49,38,65,97,76,13,27};
		sort(array, 0, array.length-1);
		printArray(array);
	}
	
	
	
	
	
	
	/**
	 * 快速排序
	 * @param array 要排序的数组
	 * @param begin 开始下标
	 * @param end   结束下标
	 */
	public void sort(int[] array,int begin,int end){
		
		int i = begin;
		int j = end;
		System.out.println("begin="+begin +",end="+ end);
		
		
		if(begin>=end){
			System.out.println("结束方法咯...");
			return;
		}
		
		
		//设置基准元素  以数组的第1个元素为关键数据 key 基准元素
		int key = array[i];
		
		
		while(true){
			//如果i和j相等就中止循环   由后往前扫
			while(j>i){
				//如果右边的数比基准元素小  需要交换位置[把j的下标对应的元素和i的下标对应的元素 交换位置]  因为排序后右边的元素都比基准元素要大
				if(array[j]<key){
					//交换位置
					changeArrayPosition(array,i,j);
					//找到一个后就结束循环   由后往前扫 变成由前往后扫
					break;
					
				}else{
					//没有替换的时候才减1. 不用替换的时候才减1
					j--;
				}
			}
			
			//如果i和j相等就中止循环   由前往后扫
			while(j>i){
				//如果左边的数比基准元素大  需要交换位置[把j的下标对应的元素和i的下标对应的元素 交换位置]  因为排序后左边的元素都比基准元素要小
				if(array[i]>key){
					//交换位置
					changeArrayPosition(array,i,j);
					//找到一个后就结束循环   由前往后扫 变成 由后往前扫
					break;
				}else{
					//没有替换的时候才加1. 不用替换的时候才加1
					i++;
				}
			}
			
			if(j==i){
				//说明已经完成了1趟的比较[左边的数都比基准元素要小，右边的数都比基准元素要大]   后面就是分成2段  再递归
				break;
			}
		}
		
		
		//基准元素的左边的元素
		sort(array, begin, i-1);
		
		//基准元素的左边的元素
		sort(array, i+1, end);
		
	}
	
	
	/**
	 * 交换数组中2个位置的数据
	 * @param min
	 * @param max
	 */
	public void changeArrayPosition(int[] array, int min,int max){
		int temp =array[min];
		array[min]=array[max];
		array[max]=temp;
		
	}
	
	/**
	 * 打印数组
	 * @param array
	 */
	public void printArray(int[] array){
		for(int index=0; index<array.length;index++){
			if(index == array.length-1){
				System.out.print(array[index]);
			}else{
				System.out.print(array[index]+", ");
			}
		}
		System.out.println();
	}

}
